翻訳と辞書 Words near each other ・ Mountain cat ・ Mountain Center, California ・ Mountain Charley ・ Mountain Cheese Olympics ・ Mountain chickadee ・ Mountain chiffchaff ・ Mountain chorus frog ・ Mountain chub ・ Mountain City ・ Mountain City Four ・ Mountain City Ranger District ・ Mountain City, Georgia ・ Mountain City, Nevada ・ Mountain City, Tennessee ・ Mountain City, Texas ・ Mountain climbing problem ・ Mountain Club of South Africa ・ Mountain coaster ・ Mountain Combat Boot ・ Mountain Communities of the Tejon Pass ・ Mountain Community Television ・ Mountain Conservation Trust of Georgia ・ Mountain Corps Norway ・ Mountain cottontail ・ Mountain County, Jefferson Territory ・ Mountain coyote ・ Mountain cranberry ・ Mountain Creek ・ Mountain Creek (disambiguation) ・ Mountain Creek (Yellow Breeches Creek) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Mountain climbing problem ： ウィキペディア英語版 Mountain climbing problem In mathematics, the mountain climbing problem is a problem of finding the conditions that two function forming profiles of a two-dimensional mountain must satisfy, so that two climbers can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while always staying at the same height. This problem was named and posed in this form by James V. Whittaker in 1966, but its history goes back to Tatsuo Homma, who solved a version of it in 1952. The problem has been repeatedly rediscovered and solved independently in different context by a number of people (see the references). In the past two decades the problem was shown to be connected to the weak Fréchet distance of curves in the plane (see ''Buchin et al.''), various planar motion planning problems in computational geometry (see ''Goodman et al.''), the square peg problem (see ''Pak''), semigroup of polynomials (see ''Baird and Magill''), etc. The problem was popularized in the article by ''Goodman et al.'', which received the MAA writing award in 1990. == Understanding the problem == It is easy to coordinate the climbers' movement between the peaks and valleys (local maxima and minima of the functions). The difficulty is that to progress, the climbers must occasionally go down the mountain, either one or the other, or both climbers. Similarly, either one or the other climber must backtrack towards the beginning of the journey. In fact, it has been observed that for a mountain with ''n'' peaks and valleys the number of turns can be as large as quadratic in ''n'' (see ''Buchin et al.''). These difficulties make the problem unintuitive and sometimes rather difficult, both in theory and in practice. == Formulation == The following result is due to Huneke: :Suppose $f$ and $g$ are continuous functions from $()$ to $()$ with $f(0)=g(0)=0$ and $f(1)=g(1)=1$, and such that neither function is constant on an interval. Then there exist continuous functions $s$ and $t$ from $()$ to $()$ with $s(0)=t(0)=0$, $s(1)=t(1)=1$, and such that $f\backslash circ\; s\; \backslash ,\; =\; \backslash ,\; g\backslash circ\; t$, where "$\backslash circ$" stands for a composition of functions. To see heuristically that the result does not extend to all continuous functions, note that if $f$ has a constant interval while $g$ has a highly oscillating interval on the same level, then the first climber would be forced to go back and forth infinitely many times, and thus can never reach the top. It is also known that for the piecewise linear functions there are no obstructions, i.e. the climbers can always coordinate their movements to get to the top (see ''Whittaker''). === Proof in the piecewise linear case === Consider a graph $G$ of all positions on a mountain both climbers can occupy on the same level. This graph is piecewise linear, i.e. a union of intervals, and can be viewed as a graph in Graph theory. Note that $G$ may or may not be connected. The vertices of the intervals correspond to peaks and valleys of the functions. There are three cases: : 1. One climber is at a peak or a valley, another climber is in between two of them, : 2. Both climbers are at a peak or at valley. : 3. One climber is at a peak and one is at valley. In the first case such vertex of $G$ has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph $G$ has all vertices of even degree, except for the point $(0,0)$ corresponding to two climbers on the bottom and the point $(1,1)$ corresponding to two climbers on top of the mountain. Applying the handshaking lemma to the connected component of $G$ containing $(0,0)$ we conclude that $(0,0)$ and $(1,1)$ are in the same connected component of $G$. This implies that there is a path from $(0,0)$ to $(1,1)$ in $G$. In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Mountain climbing problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.